#include<iostream>
#include<vector>
#include<deque>
using namespace std;

vector<int> maxSlidingWindow(vector<int>&nums, int k)
{
	int n=nums.size();
	deque<int> dq; // 辅助队列
	vector<int> ans; // 记录滑动窗口中的最大值
	
	// 处理nums前k个元素
	for(int i=0;i<k;i++)	
	{
		printf("考虑nums[%d]=%d:\n", i, nums[i]); 
		
		// 队空时将元素下标i进队尾
		if(dq.empty())
		{
			dq.push_back(i);
			printf("  %d(%d)后端进\n",i,nums[i]);
		}
		// 队不空时
		else
		{
			// 将队尾小于nums[i]的元素从队尾出队
			while(!dq.empty() && nums[i]>nums[dq.back()])
			{
				printf("  %d(%d)后端出\n",dq.back(),nums[dq.back()]); 
				dq.pop_back();
			}
			
			// 将元素下标i进队尾
			dq.push_back(i);	
			printf("  %d(%d)后端进\n",i,nums[i]);
		}
	}
	
	// 队头元素添加到ans中
	ans.push_back(nums[dq.front()]);	
	printf("ans中添加%d(i=%d)\n",ans.back(),dq.front());
	
	// 处理nums中剩余的元素
	for(int i=k; i<n; i++)
	{
		printf("考虑nums[%d]=%d:\n", i, nums[i]);
		
		// 队空时将元素下标i进队尾
		if(dq.empty())
		{
			dq.push_back(i);
			printf("  %d(%d)后端进\n",i,nums[i]);
		}
		
		// 队不空时
		else
		{
			// 将队尾小于nums[i]的元素从队尾出队
			while(!dq.empty() && nums[i]>nums[dq.back()])
			{
				printf("  %d(%d)后端出\n",dq.back(),nums[dq.back()]);
				dq.pop_back();
			}
			
			// 将元素下标i进队尾
			dq.push_back(i);	
			printf("  %d(%d)后端进\n",i,nums[i]);
		}
		
		// 将队头过期的元素从队头出队
		if(dq.front()<i-k+1)
		{
			printf("%d(%d)过期前端出\n",dq.front(),nums[dq.front()]); 
			dq.pop_front();
		}
		
		// 新队头元素添加到ans中
		ans.push_back(nums[dq.front()]);	
		printf("ans中添加%d(i=%d)\n",ans.back(),dq.front());

	}
	return ans;
}

// 打印
void disp(vector<int> &v)
{
	for(auto e:v)
		printf("%d ",e);
	printf("\n");
}
int main()
{
	vector<int> nums={4,3,5,4,3,3,6,7};
	int k=3;
	cout << "nums: ";disp(nums);
	
	// 求滑动窗口中的最大值
	vector<int> ans = maxSlidingWindow(nums,k);
	cout << "求解" << endl;
	cout << "ans: ";disp(ans);
	return 0;
}
